package 链表.双指针;


/**
 * * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?favorite=2cktkvj
 *  *
 *  * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493123&idx=1&sn=e8e882029dab35138f496a0eb425c873&chksm=9bd4180baca3911d7a54a978e52d7779164a5e44b25ef3948be59317155dd59b3030b2bff78c&scene=178&cur_album_id=2165022824317485057#rd
 */
public class _19_删除链表的倒数第N个结点 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinal = new ListNode(-1);
        sentinal.next = head;
        ListNode p = findFromEnd(sentinal,n+1);
        p.next = p.next.next;

        return sentinal.next;
    }


    public ListNode findFromEnd(ListNode head,int n) {
        if(head == null || head.next == null) return head;

        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

}
